/******************************************************************************
  DISCLAIMER:
  This software was produced by the National Institute of Standards
  and Technology (NIST), an agency of the U.S. government, and by statute is
  not subject to copyright in the United States.  Recipients of this software
  assume all responsibility associated with its operation, modification,
  maintenance, and subsequent redistribution.

  See NIST Administration Manual 4.09.07 b and Appendix I. 
*****************************************************************************/

/*

This file implements the EBNF classes defined in ebnfClasses.hh.

*/

#include "ebnfClasses.hh"
#include <string.h>       // strcmp
#include <stdio.h>

/********************************************************************/

/* definition::dup

This makes and returns a duplicate of "this" definition (same idea
as strdup).  The duplicate is as deep as the dup methods for defList
and expList make it.

*/

definition * definition::dup()
{
  return new definition((className ? strdup(className) : NULL), 
			(expressions ? expressions->dup() : NULL),
			(newDefs ? newDefs->dup() : NULL));
}

/********************************************************************/

/* defList::dup

This makes and returns a duplicate of "this" defList (same idea
as strdup).  The duplicate is as deep as the dup method for definition
makes it.

*/

defList * defList::dup()
{
  defListCell * defCell;
  defList * dupList;
  
  dupList = new defList;
  for (defCell = first; defCell; defCell = defCell->next)
    {
      dupList->pushBack(defCell->data->dup());
    }
  return dupList;
}


/********************************************************************/

/* defList::findLength

This finds the length of a defList. An empty list has length zero.

*/

int defList::findLength()
{
  int length;
  defListCell * defCell;

  length = 0;
  for (defCell = first; defCell; defCell = defCell->next)
    length++;
  return length;
}

/********************************************************************/

/* defList::insertAfterCell

If defCell is not NULL, this puts a new list cell pointing to def
after defCell.

If defCell is null, this inserts a new list cell pointing to def before
first and resets first to the new list cell.

This is not checking that defCell is a member of the list. Very bad
things will happen if it is not.

*/

void defList::insertAfterCell(
 defListCell * defCell,
 definition * def)
{
  defListCell * newCell;
  
  newCell = new defListCell(def);
  if (defCell)
    {
      newCell->next = defCell->next;
      newCell->back = defCell;
      defCell->next = newCell;
      if (newCell->next)
	newCell->next->back = newCell;
      else
	last = newCell;
    }
  else if (first)
    {
      newCell->next = first;
      // newCell->back = NULL; // it's already NULL
      first->back = newCell;
      first = newCell;
    }
  else
    { // list was empty
      // newCell->back = NULL; it is already NULL
      // newCell->next = NULL; it is already NULL
      first = newCell;
      last = newCell;
    }
}

/********************************************************************/

/* defList::pushBack

This puts a new cell at the end of the list and sets last to the
new cell.

If the list is empty at the outset, this sets first to the new cell.

*/

void defList::pushBack(definition * def)
{
  defListCell * defCell;
  
  defCell = new defListCell(def);
  if (last)
    {
      last->next = defCell;
      defCell->back = last;
    }
  else
    {
      first = defCell;
    }
  last = defCell;
}

/********************************************************************/

/* defList::pushFront

This puts a new cell at the front of the list and sets first to the
new cell.

If the list is empty at the outset, this sets last to the new cell.

*/

void defList::pushFront(definition * def)
{
  defListCell * defCell;
  
  defCell = new defListCell(def);
  if (first)
    {
      first->back = defCell;
      defCell->next = first;
    }
  else
    {
      last = defCell;
    }
  first = defCell;
}

/********************************************************************/

/* defList::removeCell

This removes a given defListCell from the defList.

If defCell is first, first is reset to the next of defCell.

If defCell is last, last is reset to the back of defCell.

This is not checking if the given defListCell is a member of the
list from which it is being removed, so be careful.

*/

void defList::removeCell(
 defListCell * defCell)
{
  if (defCell->next)
    defCell->next->back = defCell->back;
  if (defCell->back)
    defCell->back->next = defCell->next;
  if (defCell == first)
    first = defCell->next;
  if (defCell == last)
    last = defCell->back;
  delete defCell;
}

/********************************************************************/

/* expression::dup

An application may want to have constant expressions (a null
expression, for example) which are used in many places. By defining a
constant expression (such as nullExp) with global scope in an
application, it is easy to test whether an expression is a specific
constant expression (e.g. &exp == &nullExp). Constant expressions
should not be duplicated since that will make tests of the sort just
given fail. The equality test just given does not look at what is
inside the expression, so the values of the data members of a
constant expression are irrelevant.

This method enables constant expressions by providing that if theType
is 0, the function returns the "this" pointer.

Otherwise, this function makes and returns a duplicate of "this"
expression.  The duplicate is as deep as the dup method for
optional. The prodValue is not duplicated on the assumption that the
new reference should be to the same production. If a copy of the
prodValue is what the caller of this function wants, the calling
function should make the copy and the replacement itself after calling
this function.

*/

expression * expression::dup()
{
  return (theType ? new expression(theType,
				   (itemName ? strdup(itemName) : 0),
				   (attName  ? strdup(attName) : 0),
				   (optValue ? optValue->dup() : 0),
				   prodValue) :
	  this);
}

/********************************************************************/

/* expList::dup

This makes and returns a duplicate of the "this" list (same idea as
strdup).  The duplicate is as deep as the dup method for expression
makes it. At least the expression level consists of new expressions.

*/

expList * expList::dup()
{
  expListCell * expCell;
  expList * dupList;
  
  dupList = new expList;
  for (expCell = first; expCell; expCell = expCell->next)
    {
      dupList->pushBack(expCell->data->dup());
    }
  return dupList;
}

/********************************************************************/

/* expList::findLength

This finds the length of an expList. An empty list has length zero.

*/

int expList::findLength()
{
  int length;
  expListCell * expCell;

  length = 0;
  for (expCell = first; expCell; expCell = expCell->next)
    length++;
  return length;
}

/********************************************************************/

/* expList::insertAfterCell

If expCell is not NULL, this puts a new list cell pointing to exp
after expCell.

If expCell is null, this inserts a new list cell pointing to exp before
first and resets first to the new list cell.

This is not checking that expCell is a member of the list. Very bad
things will happen if it is not.

*/

void expList::insertAfterCell(
 expListCell * expCell,
 expression * exp)
{
  expListCell * newCell;
  
  newCell = new expListCell(exp);
  if (expCell)
    {
      newCell->next = expCell->next;
      newCell->back = expCell;
      expCell->next = newCell;
      if (newCell->next)
	newCell->next->back = newCell;
      else
	last = newCell;
    }
  else if (first)
    {
      newCell->next = first;
      // newCell->back = NULL; // it's already NULL
      first->back = newCell;
      first = newCell;
    }
  else
    { // list was empty
      // newCell->back = NULL; it is already NULL
      // newCell->next = NULL; it is already NULL
      first = newCell;
      last = newCell;
    }
}

/********************************************************************/

/* expList::nth

This returns the nth expression in an expList, or NULL if n is out
of range. The first expression in the list has n = 1.

*/

expression * expList::nth(int n)
{
  expListCell * expCell;
  int k;

  if (n < 1)
    return 0;
  for (k = 1, expCell = first; expCell; k++, expCell = expCell->next)
    {
      if (k == n)
	return expCell->data;
    }
  return 0;
}
/********************************************************************/

/* expList::pushBack

This puts a new cell at the end of the list and sets last to the
new cell.

If the list is empty at the outset, this sets first to the new cell.

*/

void expList::pushBack(expression * exp)
{
  expListCell * expCell;
  
  expCell = new expListCell(exp);
  if (last)
    {
      last->next = expCell;
      expCell->back = last;
    }
  else
    {
      first = expCell;
    }
  last = expCell;
}

/********************************************************************/

/* expList::pushFront

This puts a new cell at the front of the list and sets first to the
new cell.

If the list is empty at the outset, this sets last to the new cell.

*/

void expList::pushFront(expression * exp)
{
  expListCell * expCell;
  
  expCell = new expListCell(exp);
  if (first)
    {
      first->back = expCell;
      expCell->next = first;
    }
  else
    {
      last = expCell;
    }
  first = expCell;
}

/********************************************************************/

/* expList::removeCell

This removes a given expListCell from the expList.

If expCell is first, first is reset to the next of expCell.

If expCell is last, last is reset to the back of expCell.

This is not checking if the given expListCell is a member of the
list from which it is being removed, so be careful.

*/

void expList::removeCell(
 expListCell * expCell)
{
  if (expCell->next)
    expCell->next->back = expCell->back;
  if (expCell->back)
    expCell->back->next = expCell->next;
  if (expCell == first)
    first = expCell->next;
  if (expCell == last)
    last = expCell->back;
  delete expCell;
}

/********************************************************************/

/* expList::spliceInAfterCell

A. If the from list is null or empty, this prints an error message
and calls exit (the "this" list may be empty).

B. Otherwise, if expCell is null, this calls spliceInFirst.

C. Otherwise, this:
1. copies the contents of the "from" list into the "this" list
   immediately after expCell, which may not be NULL.
2. possibly resets the "last" of "this".

Example: Suppose the "this" list is (A,B,C,D), the "from" list is
(X,Y,Z), expCell is B, and (x,y,z) is a copy of (X,Y,Z), then
the following two diagrams show the before and after situations.

        expCell
           |
           v
     A <-> B <-> C <-> D                        X <-> Y <-> Z


        expCell
           |
           v
     A <-> B <-> x <-> y <-> z <-> C <-> D      X <-> Y <-> Z


Appropriate checks for resetting last are made.

The expressions in expList are duplicated before copying so
that if one is changed, other copies will not be changed.

*/

void expList::spliceInAfterCell( /* ARGUMENTS                  */
 expListCell * expCell,          /* cell after which to splice */
 expList * from)                 /* list to splice in          */
{
  expListCell * fromCell;
  expListCell * newCell;
  expListCell * previousCell;

  if ((from == NULL) || (from->first == NULL))
    {
      fprintf(stderr, "bug in expList::spliceInAfterCell\n");
      exit(1);
    }
  else if (expCell == NULL)
    spliceInFirst(from);
  else
    {
      previousCell = expCell;
      for (fromCell = from->first; fromCell; fromCell = fromCell->next)
	{
	  newCell = new expListCell(fromCell->data->dup());
	  newCell->back = previousCell;
	  newCell->next = previousCell->next;
	  previousCell->next = newCell;
	  if (newCell->next)
	    newCell->next->back = newCell;
	  else
	    last = newCell;
	  previousCell = newCell;
	}
    }
}

/********************************************************************/

/* expList::spliceInFirst

This:
1. copies the contents of the "from" list into the beginning of the
   "this" list.
2. resets the "first" of "this".
3. if "this" was empty, resets the "last" of "this".

Example: Suppose the "this" list is (B,C,D), the "from" list is
(X,Y,Z), and (x,y,z) is a copy of (X,Y,Z), then
the following two diagrams show the before and after situations.

     B <-> C <-> D                        X <-> Y <-> Z

     x <-> y <-> z <-> B <-> C <-> D      X <-> Y <-> Z

The from list should not be empty. The this list may be empty.

The expressions in expList are duplicated before copying so
that if one is changed, other copies will not be changed.

*/

void expList::spliceInFirst( /* ARGUMENTS                    */
 expList * from)             /* list to splice in            */
{
  expListCell * expCell;
  expListCell * newCell;
  expListCell * previousNewCell;

  if ((from == NULL) || (from->first == NULL))
    {
      fprintf(stderr, "bug in expList::spliceInFirst\n");
      exit(1);
    }
  expCell = from->first;
  newCell = new expListCell(expCell->data->dup());
  newCell->next = first; // will be NULL if list is empty
  // newCell->back = NULL; it is already NULL
  first = newCell;
  if (newCell->next)
    newCell->next->back = newCell;
  else // list was empty
    {
      last = newCell;
    }
  for (expCell = expCell->next; expCell; expCell = expCell->next)
    {
      previousNewCell = newCell;
      newCell = new expListCell(expCell->data->dup());
      newCell->back = previousNewCell;
      newCell->next = previousNewCell->next;
      previousNewCell->next = newCell;
      if (newCell->next)
	newCell->next->back = newCell;
      else // list was empty
	last = newCell;
    }
}

/********************************************************************/

/* expList::uses

Called By:
  production::findUsedIn
  uses (recursively)

This returns true if "this" expList contains an expression whose
itemName is the same as the name of the the "prod" production. It
also returns true if "this" explist contains an optional and a
recursive call of this method applied to the expressions of the
optional returns true. Otherwise, it returns false.

This also inserts prod as the prodValue of any expression in "this"
list if the itemName of the expression is the same as the name
of the production. Because of this secondary functionality, the
function does not return as soon as it determines it should return
true.

*/

bool expList::uses(
 production * prod)
{
  expListCell * expCell;
  bool retVal;

  retVal = false;
  for (expCell = first; expCell; expCell = expCell->next)
    {
      if (expCell->data->optValue)
	{
	  if (expCell->data->optValue->expressions->uses(prod))
	    retVal = true;
	}
      else if (expCell->data->itemName == NULL); // might be NULL (NEWLINE)
      else if (strcmp(expCell->data->itemName, prod->lhs) == 0)
	{
	  retVal = true;
	  expCell->data->prodValue = prod;
	}
    }
  return retVal;
}

/********************************************************************/

/* optional::dup

This makes and returns a duplicate of the "this" optional (same idea
as strdup).  The duplicate is as deep as the dup method for expList
makes it.

*/

optional * optional::dup()
{
  return new optional(expressions->dup(), digit);
}

/********************************************************************/

/* production::findInnerList

The returns the number of productions that are lists and occur in the
definitions of "this" production. The "this" production is expected
usually to be the list item of a list, but that is not required.

Lists that appear inside optionals are not counted.

*/

int production::findInnerList()
{
  defListCell * defCell;
  expListCell * expCell;
  int howMany;
  
  howMany = 0;
  for (defCell = defs->first; defCell; defCell = defCell->next)
    {
      expCell = defCell->data->expressions->first;
      for ( ; expCell; expCell = expCell->next)
	{
	  if (expCell->data->prodValue && expCell->data->prodValue->isList)
	    { // found a list
	      howMany++;
	    }
	}
    }
  return howMany;
}

/********************************************************************/

/* production::findIsList

findIsList decides if a production is a list (in a specific format),
returning 1 if it is a list with commas, 2 if it is a list without
commas and 0 if not. A production is judged to be a list if:
1. It has one definition, and
2. the expression list in the definition contains two expressions, and
3. the first expression in the definition is an optional, and
4. the expression list in the optional has 1 or 2 entries, and
5. the first expression in the optional has a name that is the same
   as the lhs (left-hand side) of the production.

The following production is a prototypical example of an EBNF
production defining a type 2 list.

intList =
	  [intList , c] , intVal
	;

Note that this requires that all lists use left recursion and all
lists define a list item (the second expression in the definition).

It might be useful to add the requirement that if the expression list
in the optional has two expressions, the second is a comma, but the
notion of a comma is outside the scope of EBNF classes.

It is anticipated that operations on productions that define lists will
change how they are defined (by changing to right recursion, for example)
but will not change the fact that they are lists. Thus, it will be
useful to set isList when a production is first read (or otherwise
created) and to leave it set that way until and unless the list is
modified

*/

int production::findIsList()
{
  expression * exp;
  int length;

  if (defs->findLength() != 1)
    return 0;
  if (defs->first->data->expressions->findLength() != 2)
    return 0;
  exp = (defs->first->data->expressions->first->data);
  if ((exp->optValue == NULL) ||
      (exp->optValue->digit != 1) ||
      (exp->optValue->expressions == NULL))
    return 0;
  length = exp->optValue->expressions->findLength();
  exp = exp->optValue->expressions->first->data;
  return (strcmp(lhs, exp->itemName) ? 0 :
	  (length == 1) ? 1 :
	  (length == 2) ? 2 : 0);
}

/********************************************************************/

/* production::findOuterList

This returns the number of productions that are lists and have list
items that use "this" production. If there is one or more such outer
list, the function also sets *outerList to point to the first one.

For this function to work, lists must be represented using the
following method.

aList = [aList , c] , aListItem ;

aListItem = whatever ;

*/

int production::findOuterList(
 production ** outerList)
{
  prodListCell * prodCellA;
  prodListCell * prodCellB;
  int howMany;
  
  howMany = 0;
  for (prodCellA = usedIn.first; prodCellA; prodCellA = prodCellA->next)
    {
      prodCellB = prodCellA->data->usedIn.first;
      for ( ; prodCellB; prodCellB = prodCellB->next)
	{
	  if (prodCellB->data->isList)
	    {
	      howMany++;
	      if (howMany == 1)
		*outerList = prodCellB->data;
	    }
	}
    }
  return howMany;
}

/********************************************************************/

/* production::findUsedIn

findUsedIn finds which productions "this" production is used in and
puts them into the usedIn list of "this".

For a list L, the usedIn list of L does not include L.

This does not stop processing the defs once it has been determined
that "this" production is used in one of the defs because the "uses"
method of expList needs to be run on all of the defs in order to
set the prodValue of all expressions that have a prodValue.

*/

void production::findUsedIn(prodList * productions)
{
  prodListCell * prodCell;
  defListCell * defCell;
  defList * defs;

  for (prodCell = productions->first; prodCell; prodCell = prodCell->next)
    {
      if (prodCell->data == this)
	continue; // don't check to see if a production uses itself
      defs = prodCell->data->defs;
      for (defCell = defs->first; defCell; defCell = defCell->next)
	{
	  if (defCell->data->expressions->uses(this) == true)
	    {
	      if ((usedIn.last == NULL) ||
		  (usedIn.last->data != prodCell->data))
		usedIn.pushBack(prodCell->data);
	    }
	}
    }
}

/********************************************************************/

/* production::production


*/

production::production(
 char * lhsIn,
 defList * defsIn)
{
  defs = defsIn;
  endsInOptional = false;
  fixType = fixNone;
  isSupertype = false;
  lhs = lhsIn;
  subtypeOf.first = 0;
  subtypeOf.last = 0;
  usedIn.first = 0;
  usedIn.last = 0;
  wasPrinted = false;

  isList = findIsList();
}

/********************************************************************/

/* prodList::findLength

This finds the length of a prodList. An empty list has length zero.

*/

int prodList::findLength()
{
  int length;
  prodListCell * prodCell;

  length = 0;
  for (prodCell = first; prodCell; prodCell = prodCell->next)
    length++;
  return length;
}

/********************************************************************/

/* prodList::findUsedIn

*/

void prodList::findUsedIn()
{
  prodListCell * prodCell;

  for (prodCell = first; prodCell; prodCell = prodCell->next)
    {
      prodCell->data->findUsedIn(this);
    }
}

/********************************************************************/

/* prodList::insertAfterCell

If prodCell is not NULL, this puts a new list cell pointing to prod
after prodCell.

If prodCell is null, this inserts a new list cell pointing to prod before
first and resets first to the new list cell.

This is not checking that prodCell is a member of the list. Very bad
things will happen if it is not.

*/

void prodList::insertAfterCell(
 prodListCell * prodCell,
 production * prod)
{
  prodListCell * newCell;
  
  newCell = new prodListCell(prod);
  if (prodCell)
    {
      newCell->next = prodCell->next;
      newCell->back = prodCell;
      prodCell->next = newCell;
      if (newCell->next)
	newCell->next->back = newCell;
      else
	last = newCell;
    }
  else if (first)
    {
      newCell->next = first;
      // newCell->back = NULL; // it's already NULL
      first->back = newCell;
      first = newCell;
    }
  else
    { // list was empty
      // newCell->back = NULL; it is already NULL
      // newCell->next = NULL; it is already NULL
      first = newCell;
      last = newCell;
    }
}

/********************************************************************/

/* prodList::pushBack

This puts a new cell at the end of the list and sets last to the
new cell.

If the list is empty at the outset, this sets first to the new cell.

*/

void prodList::pushBack(
 production * prod)
{
  prodListCell * prodCell;
  
  prodCell = new prodListCell(prod);
  if (last)
    {
      last->next = prodCell;
      prodCell->back = last;
    }
  else
    {
      first = prodCell;
    }
  last = prodCell;
}

/********************************************************************/

/* prodList::removeCell

This removes a given prodListCell from the prodList.

If prodCell is first, first is reset to the next of prodCell.

If prodCell is last, last is reset to the back of prodCell.

This is not checking if the given prodListCell is a member of the
list from which it is being removed, so be careful.

*/

void prodList::removeCell(
 prodListCell * prodCell)
{
  if (prodCell->next)
    prodCell->next->back = prodCell->back;
  if (prodCell->back)
    prodCell->back->next = prodCell->next;
  if (prodCell == first)
    first = prodCell->next;
  if (prodCell == last)
    last = prodCell->back;
  delete prodCell;
}

/********************************************************************/

/* prodList::removeProd

This removes from the prodList the first prodListCell (call it prodCell)
whose data points to prod, if there is any such prodListCell.

If prodCell is first, first is reset to the next of prodCell.

If prodCell is last, last is reset to the back of prodCell.

*/

void prodList::removeProd(
 production * prod)
{
  prodListCell * prodCell;
  
  for (prodCell = first; prodCell; prodCell = prodCell->next)
    {
      if (prodCell->data == prod)
	{
	  if (prodCell->next)
	    prodCell->next->back = prodCell->back;
	  if (prodCell->back)
	    prodCell->back->next = prodCell->next;
	  if (prodCell == first)
	    first = prodCell->next;
	  if (prodCell == last)
	    last = prodCell->back;
	  delete prodCell;
	  break;
	}
    }
}

/********************************************************************/

/* prodList::member

member looks for prod in "this" prodList. If prod is found, member
returns a pointer to the first prodListCell pointing at prod. If prod
is not found, member returns NULL.

*/

prodListCell * prodList::member(production * prod)
{
  prodListCell * prodCell;
  
  for (prodCell = first; prodCell; prodCell = prodCell->next)
    {
      if (prodCell->data == prod)
	break;
    }
  return prodCell;
}

/********************************************************************/

/* stringCell::record

The record method puts the dataIn string into a list in alphabetical order.

*/

void stringCell::record(
 char * dataIn)
{ // keeps list in alphabetical order, ignores duplicates
  stringCell * aCell;
  stringCell * newCell;
  stringCell * backCell;
  int compVal;
  
  if (data == 0)
    { // happens when first entry is made
      data = dataIn;
      return;
    }
  compVal = strcmp(dataIn, data);
  if (compVal < 0)
    { // dataIn comes first, so need to shift
      newCell = new stringCell(data);
      data = dataIn;
      newCell->next = next;
      next = newCell;
      return;
    }
  else if (compVal == 0)
    { // ignore duplicate
      return;
    }
  backCell = this;
  for (aCell = next; aCell; aCell = aCell->next)
    {
      compVal = strcmp(dataIn, aCell->data);
      if (compVal < 0)
	{ // new cell goes immediately before aCell
	  newCell = new stringCell(dataIn);
	  backCell->next = newCell;
	  newCell->next = aCell;
	  return;
	}
      else if (compVal == 0)
	{ // ignore duplicate
	  return;
	}
      backCell = aCell;
    }
  // new cell must go at the end, since we haven't returned yet
  newCell = new stringCell(dataIn);
  backCell->next = newCell;
}

/********************************************************************/

